#include "stdio.h"
#include "string.h"
int shu[100][100],ins[100],chu[100];



void count3(int *t,int *to)
{
	int i,len;
	memset(to,0,sizeof(to));
	len=t[0];
	for (i=1;i<=len;i++)
	{
		to[i]+=t[i]*3;
		if (to[i]>9)
		{
			to[i+1]+=to[i]/10;
			to[i]%=10;
		}
	}
	while (to[len+1]!=0) 
		len++;	
	to[0]=len;	
}

void ex(char *s)
{
    int i,len;
    memset(ins,0,sizeof(ins));
    len=strlen(s);
    for (i=len-1;i>=0;i--)
        ins[len-i]=s[i]-'0';
    ins[0]=len;    
}    

int get2()
{
    int i,shi,yu,to[100],len;
    len=ins[0];
    memset(to,0,sizeof(to));
    yu=0;
    for (i=len;i>=1;i--)
    {
        yu=yu*10+ins[i];
        to[i]=yu/2;
        yu%=2;    
    }
    while (to[len]==0&&len>1) len--;
    to[0]=len;
    memcpy(ins,to,sizeof(to));
    return yu;    
}

void jian()
{
    int i,len;
    len=chu[0];
    chu[1]--;
    for (i=1;i<len;i++)
        if (chu[i]<0)
        {
                chu[i]+=2;
                chu[i+1]--;    
        }    
    if (chu[len]==0&&len>=1) len--;
    chu[0]=len;
}

main()
{
	int i,j,flag;
	char s[100];
	memset(shu,0,sizeof(shu));
	i=shu[4][0];
	shu[1][0]=1;
	shu[1][1]=1;
	for (i=2;i<=100;i++)
		count3(shu[i-1],shu[i]);
/*	for (i=shu[4][0];i>=1;i--) 
		printf("%d",shu[4][i]);
	printf("\n"); */
	
	
	while (1)
	{
	    scanf("%s",s);
	    if (s[0]=='0') break;
	   	ex(s);
	   	chu[0]=0;
	   	while (1)
	   	{
             if (ins[0]==1&&ins[1]==0) break;
             chu[0]++;
             chu[chu[0]]=get2(); 
        }       
        
        jian();
        printf("{");
        if (!(s[0]==1&&strlen(s)==1))
        {
            flag=0;
                for (i=1;i<=chu[0];i++)
                    if (chu[i])
                    {
                        if (flag) printf(",");
                        else flag=1;  
                        printf(" ");
                         
                        for (j=shu[i][0];j>=1;j--) 
                           printf("%d",shu[i][j]);                                        
                    }    
        }
        printf(" }\n");
        
	}   	

	return 0;
}













					
					
					
					